-- file zs5/MyFabonacci.hs
module MyFibonacci where

-- ================ total argumenting recursion 扩展递归

total [] = 0
total (x : xs) = x + total xs

-- ================ total 尾递归优化
total1a [] n = n
total1a (x : xs) n = total1a xs (n + x)

total1 xs = total1a xs 0

-- ================ total 尾递归优化; 并且强制计算参数
total2 [] n = n
-- total2 (x : xs) !n = total2 xs (x + n)
total2 (x : xs) n = total2 xs $! (x + n)

-- ================ John McCarthy 91 函数
mc n
  | n > 100 = n - 10
  | otherwise = mc (mc (n + 11))

-- ================ Fib.hs Fibonacci array
fibonacci :: (Num a, Eq a) => a -> a -- 数字类型的模式匹配需要Eq类型类
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = fibonacci (n - 1) + fibonacci (n - 2)

fibs2 :: (Num b, Eq b, Enum b) => b -> [b]
fibs2 n = map fibonacci [0 .. n]

-- ================ 使用 tuple，加速计算
fibStep :: (Num a) => (a, a) -> (a, a)
fibStep (u, v) = (v, u + v)

fibPair :: (Eq a, Num a) => a -> (a, a)
fibPair 0 = (0, 1)
fibPair n = fibStep (fibPair (n - 1))

-- ================ 或者定义为 fastFib n = fst (fibPair n)
fastFib :: (Eq b, Num b) => b -> b
-- 取出第一个元素
fastFib n = fst $ fibPair n

-- 这样，把函数 fibs 改成了
-- 读者可以思考一下fibs的类型签名，它为什么需要三个类型类限定
-- fibs2 :: (Enum b, Eq b, Num b) => b -> [b]
fibs :: (Eq b, Num b, Enum b) => b -> [b]
fibs n = map fastFib [1 .. n]

-- ================ 使用 iterate 加速
fibs3 :: (Num b) => Int -> [b]
fibs3 n = take n (map fst (iterate fibStep (0, 1)))

-- ================ 使用 iterate 加速
fibs3b :: (Num a) => Int -> [(a, a)]
fibs3b n = take n (iterate fibStep (0, 1))

-- ================ 黄金分割率
golden :: (Fractional a) => Int -> [a]
golden n = take n (map (\(x, y) -> x / y) (iterate fibStep (0, 1)))

-- ================ 尾递归优化版
fib4 0 f1 f2 = f2
fib4 n f1 f2 = fib4 (n - 1) f2 (f1 + f2)

fibonacci4 n = fib4 n 1 1

-- ================ 生成三元组, 验证 中间项平方与外两 项之积是差 1 的
combine :: [(a, a)] -> [(a, a, a)]
combine ((f1, f2) : (f3, f4) : fs) = (f1, f2, f4) : combine ((f3, f4) : fs)
combine _ = []

fibPairs :: Int -> [(Int, Int)]
fibPairs n = map fibPair [1 .. n]

-- 验证 中间项平方与外两 项之积是差 1 的
difference :: Int -> [Int]
difference n = map (\(f1, f2, f3) -> f1 * f3 - f2 * f2) (combine $ fibPairs n)

difference2 n = map (\(f1, f2, f3) -> f1 * f3 - f2 * f2) (combine $ fibs3b n)

-- ================ 转换为罗马数字
-- 这里只考虑 5000 以内的罗马数字。先来定义两个列表，分别对应罗马数字和与之对应的十进制数。
romeNotation :: [String]
romeNotation = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]

romeAmount :: [Int]
romeAmount = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]

-- 使用 zip 函数将它们结合在一起
pair :: [(Int, String)]
pair = zip romeAmount romeNotation

-- 从 pair 列表中取得第一个比这个十进制小的数字
subtrahend :: Int -> (Int, String)
subtrahend n = head (dropWhile (\(a, _) -> a > n) pair)

-- 递归转换
convert :: Int -> String
convert 0 = ""
convert n =
  let (rome, m) = subtrahend n
   in m ++ " " ++ convert (n - rome)